/*a*k−10*q=r−s1
​裴蜀定理 指出，该方程有解，当且仅当 r−s1是 g=gcd(a,10)的倍数，即r≡s1(modg)
*/
class Solution {
public:
    int n, step, g;
    void modify(int start, string &t) {
        int ch=t[start]-'0'; //最靠前的数字
        //ch最小可以变为ch%g
        int inc=ch%g-ch+10; 
        for(int j=start; j<n; j+=2) t[j]='0'+(t[j]-'0'+inc)%10;
    }

    string findLexSmallestString(string s, int a, int b) {
        n=s.size(), step=gcd(b, n), g=gcd(a, 10); //最小可以移动的步数 最小累加值
        string ans;
        for(int i=0; i<n; i+=step) {
            string t=s.substr(i)+s.substr(0, i); //轮转
            modify(1, t); //累加所有奇数下标
            if(step&1) modify(0, t); //累加所有偶数下标
            if(ans.empty()||t<ans) ans=move(t);
        }
        return ans;
    }
};